#include <bits/stdc++.h>

using namespace std;
/**
    1 <= nums.length <= 10
    0 <= nums[i] <= 1000
    1 <= queries.length <= 1000
    queries[i] = [li, ri, vali]
    0 <= li <= ri < nums.length
    1 <= vali <= 10
 */
class Solution
{
    int canReduceToZero(const vector<int> &idx, const vector<int> &mm, int num)
    {
        if(num == 0) return 0;
        int minIndex = -1;
        int n = mm.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(num + 1, false)); // dp[i][j] 表示能否用前 i 个元素凑出 j
        dp[0][0] = true;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= num; j++)
            {
                if (dp[i][j])
                {
                    dp[i + 1][j] = true;
                    if (j + mm[i] <= num)
                        dp[i + 1][j + mm[i]] = true;
                }
            }
            if (dp[i + 1][num])
            {
                return idx[i] + 1;
            }
        }
        return -1;
    }

public:
    int minZeroArray(vector<int> &nums, vector<vector<int>> &queries)
    {
        int k = -1;
        for(int i = 0; i < nums.size();++i){
            vector<int> hh;
            vector<int> idx;
            for(int qi = 0; qi < queries.size(); ++qi){
                auto & q = queries[qi];
                int l = q[0], r = q[1], v = q[2];
                if(l <= i && i <= r){
                    hh.push_back(v);
                    idx.push_back(qi);
                }
            }
            int kk = canReduceToZero(idx, hh,nums[i]);
            if(kk != -1){k = max(k,kk);}
            else return -1;
        }
        return k;
    }
};

int main()
{

    // system("pause");
    return 0;
}
